package tree

//给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
//注意：两结点之间的路径长度是以它们之间边的数目表示
// 方法：深度优先搜索
func DiameterOfBinaryTree(root *Node) int {
	var depth func(*Node) int
	var maxVal int //保留最大值
	depth = func(node *Node) int {
		//check node
		if node == nil {
			return 0
		}

		//divide
		l := depth(node.Left)
		r := depth(node.Right)

		//conquer,可能经过根节点
		if (l + r) > maxVal {
			maxVal = l + r
		}

		//返回最大值
		return max(l, r) + 1
	}
	depth(root)
	return maxVal
}
